#include <iostream>
using namespace std;
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * 改进版本相较于原版本，时间复杂度大大降低，但是由于创建了新的链表，所以空间复杂度仍然很高
 * 后续可以通过在原有链表上做修改，进行改进
 */
class Solution {
public:
  ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {

    ListNode *dummy, *current;
    dummy = current = new ListNode(0);

    int data, carry = 0, v1, v2, temp;
    while (l1 || l2) {
      v1 = l1 ? l1->val : 0;
      v2 = l2 ? l2->val : 0;
      temp = v1 + v2 + carry;
      data = temp % 10;
      carry = temp / 10;
      current->next = new ListNode(data);
      current = current->next;
      if (l1)
        l1 = l1->next;
      if (l2)
        l2 = l2->next;
    }

    if (carry > 0) {
      current->next = new ListNode(1);
    }
    return dummy->next;
  }
};
int main() {
  ListNode *t = new ListNode(0);
  ListNode *s = new ListNode(0);

  return 0;
}
